|
A classical approach to solve the Hypergraph bipartitioning problem is an iterative heuristic by Fiduccia and Mattheyses. This heuristic is commonly called the FM algorithm. == Introduction == FM algorithm is a linear time heuristic for improving network partitions. New features to K-L heuristic: * Aims at reducing net-cut costs; the concept of cutsize is extended to hypergraphs. * Only a single vertex is moved across the cut in a single move. * Vertices are weighted. * Can handle "unbalanced" partitions; a balance factor is introduced. * A special data structure is used to select vertices to be moved across the cut to improve running time. * Time complexity O(P), where P is the total # of terminals. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Fiduccia-Mattheyses algorithm」の詳細全文を読む スポンサード リンク
|